As promised in my previous post, here is my intersection routine. You
cannot use it directly as it's a C++-ified version, but i think you'll
get the general idea behind it. It's *much* faster than the original
version.

//============================================================================
// CSG_INTERSECTION::AllObjectIntersections:
//
//    Author: POV-Ray Team

/*  AKA:
    To get an intersection for a CSG-Intersection object, it must be
    contained within all objects (TODO: if the given objects don't
    overlap anywhere, detect it during the parsing stage.)
    So the original algorithm loops twice over all objects:
      The outer loop retrieves all intersection points for each of the
      objects.
      The inner loop checks, whether any of these intersections is
      inside of all other objects (which would lead to a hit).
    It's short and simple, bot not very effective. 
    Imagine i.e. the following difference object,
    
    difference
      {
      union { ...} // A complex union
      object { small_sphere1 }
      ...
      object { small_sphere1000 }

      ... // texture etc.
      }

    to create a sponge. Assume a ray that results in 1000 intersection
    points from the union, but no hit for the inverted small spheres.
    The latter means: No hit but the ray's origin is inside of each of
    the inverted spheres, so the entire ray is inside of each of the
    spheres.
    ==> It's not necessary do any sphere-inside-test for any of the
        intersection points.

    I changed it to three independend steps:
    
    1. Retrieve all intersections of the not-inverted children:
       If a child is not intersected:
         if ray's origin is outside of this child, the whole CSG isn't
         intersected, else the entire ray is inside of this child, so
         it can be ignored completely in 3.
       Else, the intersections and the child are stored for step 3.
    2. Same as 1. for all inverted children.
       They are handled seperately because of a BBOX tree effectively
       speeds up calculations:
       If a finite node isn't hit, we can ignore any of it's leaf
       objects as the entire ray must be inside of each leaf object.
       This saves a lot of intersection tests.
    3. Each intersection, that is inside of each of the children
       retrieved above, is a valid CSG intersection.

    It doesn't make sense to use the not-inverted children in a BBOX
    tree. The CSG's BBOX is computed as the intersection of all
    not-inverted children bounding boxes.
    If a ray hit's the CSG's BBOX, it will also hit each BBOX of each
    not-inverted child.
*/

bool CSG_INTERSECTION::AllObjectIntersections(RAY &Ray, ISTACK
*Depth_Stack, DBL BestDepth) const
  {
  bool maybeFound(false), found(false), escape(false),
rayFlagsTest(false);
  OBJECT *o;
  int childIdx;
  void *IntersectionCSG = GetFlagMultiTextured() ? (void*) this :
NULL;

  Increase_Counter(stats[Ray_CSG_Intersection_Tests]);
  
  OBJECTLIST *hitQueue   = ObjectListPool.Request();
  ISTACK     *localStack = IstackPool.Request();
  
  // First stage: 
  // Test all not-inverted objects, try to escape as early as
possible.
  for (childIdx = 0; !escape && (childIdx < m_notInvChildren.size());
++childIdx)
    {
    o = m_notInvChildren[childIdx];

    if (o->AllIntersections(Ray, localStack, BOUND_HUGE))
      hitQueue->push_back(o);
    else
      {
      if (!o->Inside(Ray.Initial))
        {
        // The entire ray is outside of >o<, we can escape now.
//        SetAsFirstSib(childIdx);
        escape = true;
        }
      // else the ray starts from within >o< never hitting any
      // boundary, it can be ignored completely.
      }
    }

  // Second stage: Get all intersections of the inverted objects
  if (!escape)
    {
    if (BBox_Tree != NULL)
      escape = IntersectCsgIntersectionTree(BBox_Tree, hitQueue, Ray,
localStack);
    else
      {
      // No BBox Tree of inverted siblings, step through children
list.
      for (childIdx = 0; !escape && (childIdx < Children.size());
++childIdx)
        {
        o = Children[childIdx];

        // Test objects AABB before intersection test
        if (!o->BBoxTestPassed(Ray, BOUND_HUGE))
          {
          // no AABB hit
          if (!o->Inside(Ray.Initial))  // entire ray is outside of
>o<
            escape = true;

          continue; // with next object or escape
          }

        if (o->AllIntersections(Ray, localStack, BOUND_HUGE))
          hitQueue->push_back(o);
        else
          {
          if (!o->Inside(Ray.Initial))
            {
            escape = true;
            break;
            }
          }
        }
      }
    }

  // Third stage: Now we have a list of intersections in 'localStack'
and a
  // list of intersected objects in 'hitQueue'.
  // Get all intersections, that are inside of all objects.
  if (!escape)
    {
    for (int i = 0; i < localStack->size(); ++i)
      {
      maybeFound            = true; // new intersection to be checked
      INTERSECTION &locIsec = (*localStack)[i];
      const OBJECT *obj     = locIsec.Object;
      VECTOR       &iPoint  = locIsec.IPoint;

      if ((locIsec.Depth < BestDepth) && PointInClip(iPoint))
        {
        for (int j = 0; j < hitQueue->size(); ++j)
          {
          const OBJECT *hitObject = (*hitQueue)[j];

          if ((hitObject != obj) && !hitObject->Inside(iPoint))
            {
            maybeFound = false; // missed object '(*hitQueue)[j]'
            break;              // try the next intersection
            }
          }

        if (maybeFound)
          {
          found = true;
          INTERSECTION &isec = push_copy(Depth_Stack, locIsec);
          isec.Object = this;
          if (NULL != locIsec.Csg) // the child is a CSG itself
            isec.Csg = locIsec.Csg;
          else // it was a simple child
	        isec.Csg = locIsec.Object;
          }
        }
      }
    }
  
  IstackPool.Release(localStack);
  ObjectListPool.Release(hitQueue);
  
  if (found)
    Increase_Counter(stats[Ray_CSG_Intersection_Tests_Succeeded]);
  
  return(found);
  }

Post a reply to this message